1. Field of the Invention
The present invention relates to a system and a method extensible for performing stereo matching in real-time, and more particularly relates to a system and a method extensible for performing, in real-time, stereo matching fox calculating depth images with a result of searching for points of similarity by using images taken with two cameras.
2. Description of the Prior Art
In a case where images are taken with two cameras, because of the difference in the respective distances between two cameras and the different focal distances, the same object comes to appear in positions different from each other in two images.
For example, let's suppose that the two cameras take images so that a first object close to a camera and a second object fax away from the camera are included in one image. Because the first object is affected by the distance difference between the two cameras, the first object is located in a different position in the two taken images, whereas the second object is located in a similar position in the two taken images.
A scheme of using this phenomenon is to search for pixels of the first and second images in order to check which pixel of the second image is the most similar to a pixel of the first image. A result of the search makes it possible to acquire depth information of the object included in the images.
However, in the case of carrying out an operation of stereo vision, due to a large amount of search and operation, stereo matching for searching the two images for the same points is faced with difficulties.
In a case of gray images, the value of each pixel is set to one of 0 to 255, and therefore, innumerable repetition occurs. On this account, if a comparison is made between only the pixels in calculating correlation of pixels constructing the two images, correct results are not attained.
Accordingly, one pixel and surrounding pixels are grouped into a set, and then a comparison should be made between sets. As this comparison should be repeated with respect to each pixel by a distance difference between objects whose information is to be obtained from images, the amount of calculation increases by a great deal.
The stereo matching method that is generally the most widely known includes a Sum of Absolute Differences (SAD) method and a census method.
In the SAD method, a first pixel and its surrounding pixels of a first image taken with a left camera are grouped into a first set of pixels, and a second set of pixels in specified of a second image taken with a right camera, located in the same row and having the same size as the row and the size of the first set of pixels. Then, the difference between gray values of the first and second set of pixels is evaluated, and the absolute value of the evaluated difference between the grey values is set for correlation between the first and second pixels.
In one census method, census transform is performed between a first pixel and its surrounding pixels of a first image taken with a left camera. In the same manner, the census transform is performed between a second pixel and its surrounding pixels of a first image taken with a left camera. Then, both the first pixel and its surrounding pixels and the second pixel and its surrounding pixels, to which the census transforms, are respectively applied, are grouped into a first set. In addition, the census transform is performed between a third pixel and its surrounding pixels of a second image taken with a right camera. In the same manner, the census transform is performed between a fourth pixel and its surrounding pixels of a second image taken with a right camera. Then, both the third pixel and its surrounding pixels and the fourth pixel and its surrounding pixels, to which the census transforms are respectively applied, are grouped into a second set. Thereafter, an operation of exclusive OR (XOR) is performed on the first and second sets, and a value obtained by carrying out an operation of XOR is set for correlation between the first and second sets.
Because both the SAD method and the census method require a great quantity of operations, in a case where a computer system adopting a general-purpose microprocessor carries out the operations, the computer system bears an enormous load of the operations, and hardly carries out the operations in real-time.
A prior stereo Hatching method is disclosed in the Korean Public Patent Publication No. 10-2003-0015625, published on Feb. 25, 2003.
As shown in FIG. 1, the above-stated stereo matching method of No. 10-2003-0015625 includes the steps of (S1) taking an image of a scene in which a light having the shape of a line radiated from a light plane projector illuminates the object inside a frame having the shape of a regular hexahedron; (S2) detecting a Light Emitting Diode (LED) adhered to the cube-shaped frame from the taken image, and setting a coordinate on the basis of a detected position; (S3) calculating three-dimensional coordinates by Linux Documentation Project (LDP) calculating coordinates of a position in which a light plane meets a corner of the cube-shaped frame; (S4) converting a stripe of the light into a narrow line; (S5) computing three-dimensional coordinates of the object by computing coordinates of the stripe of the light formed in a case where the object meets the light plane; (S6) applying a triangle extraction algorithm to a set of points on the surface of the object, and generating a triangle network structure; and (S7) eliminating, by using a normal vector, a triangle which has been incorrectly formed.
Another prior stereo matching method is disclosed in the Korean Public Patent Publication No. 10-2006-0006189, published on Jan. 19, 2006.
As shown in FIG. 2, the aforementioned stereo matching method of No. 10-2006-0006189 includes the steps of (S10 and S20) differentiating resolutions of stereo images from one another, and finding multi-level images; (S30) taking a map of a disparity out of an image having a level corresponding to the lowest rank resolution; (S40) estimating a rough map of the disparity with, respect to an image of an upper level from the map of the disparity; (S50) taking a fine map of the disparity with respect to the image of the upper level out of the rough map of the disparity; (S60) if the image of the upper level corresponds to an image having a resolution of the highest level; and (S70) outputting the fine map of the disparity as the last map of the disparity related to the stereo image.
Furthermore, to cite an example of the literature of an adaptive window, there is “A Stereo Matching Algorithm with Adaptive Window,” and to give an example of the literature of a multi-view, there is “Multiple View Geometry in Computer Vision.”
Still, the arts disclosed in the above Patent Publications and the literature relate to methods for performing the stereo matching, and are implemented with general-purpose computers. They relate to methods for obtaining three-dimensional information irrespective of the speed or the implementation methods.
Consequently, since the aforementioned arcs do not take carrying out the stereo matching in real-time into account, problems have appeared in that they are hardly applied to actual intellectual-type robots and industrial settings.